{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Path Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minPathSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小路径和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个包含非负整数的 <code><em>m</em>&nbsp;x&nbsp;<em>n</em></code>&nbsp;网格&nbsp;<code>grid</code> ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。</p>\n",
    "\n",
    "<p><strong>说明：</strong>每次只能向下或者向右移动一步。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/05/minpath.jpg\" style=\"width: 242px; height: 242px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,3,1],[1,5,1],[4,2,1]]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>因为路径 1→3→1→1→1 的总和最小。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,2,3],[4,5,6]]\n",
    "<strong>输出：</strong>12\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 200</code></li>\n",
    "\t<li><code>0 &lt;= grid[i][j] &lt;= 200</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-path-sum](https://leetcode.cn/problems/minimum-path-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-path-sum](https://leetcode.cn/problems/minimum-path-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,3,1],[1,5,1],[4,2,1]]', '[[1,2,3],[4,5,6]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(1, m):\n",
    "            grid[i][0] += grid[i-1][0]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            grid[0][i] += grid[0][i-1]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                grid[i][j] += min(grid[i-1][j], grid[i][j-1])\n",
    "        \n",
    "\n",
    "\n",
    "        # l_v = u_v = 0\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         if i == 0 and j == 0:\n",
    "        #             u_v = l_v = 0\n",
    "        #         elif i == 0 and j != 0:\n",
    "        #             l_v = u_v = grid[i][j-1]\n",
    "        #         elif i != 0 and j != 0:\n",
    "        #             u_v = grid[i-1][j]\n",
    "        #             l_v = grid[i][j-1]\n",
    "        #         elif j == 0 and i != 0:\n",
    "        #             l_v = u_v = grid[i-1][j]\n",
    "        #         grid[i][j] += min(l_v, u_v)\n",
    "        return grid[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: 'List[List[int]]') -> 'int':\n",
    "            m, n = len(grid), len(grid[0])\n",
    "            dp = [0] + [sys.maxsize] * (n-1) #注意这句话，如果写成dp = [0] * n就是错的\n",
    "\n",
    "            for i in range(m):\n",
    "                dp[0] = dp[0] + grid[i][0]\n",
    "                for j in range(1, n):\n",
    "                    dp[j] = min(dp[j-1], dp[j]) + grid[i][j]\n",
    "\n",
    "            return dp[-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dp = [grid[0][0]]\n",
    "        for j in range(1, len(grid[0])):\n",
    "            dp.append(dp[j-1] + grid[0][j])\n",
    "            #print(dp[j])\n",
    "        for i in range(1, len(grid)):\n",
    "            dp[0] += grid[i][0]\n",
    "            #print(dp[0])\n",
    "            for j in range(1, len(grid[0])):\n",
    "                dp[j] = min(dp[j], dp[j-1]) + grid[i][j]\n",
    "                #print(dp[j])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not grid or not grid[0]:\n",
    "            return 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if i > 0 or j > 0:\n",
    "                    if i == 0:\n",
    "                        grid[i][j] += grid[i][j-1]\n",
    "                    elif j == 0:\n",
    "                        grid[i][j] += grid[i-1][j]\n",
    "                    else:\n",
    "                        grid[i][j] += min(grid[i-1][j], grid[i][j-1])\n",
    "        return grid[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: 'List[List[int]]') -> 'int':\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if j == n - 1:\n",
    "                    right = float('inf')\n",
    "                    if i == m - 1:\n",
    "                        continue\n",
    "                else:\n",
    "                    right = grid[i][j + 1]\n",
    "                if i == m - 1:\n",
    "                    down = float('inf')\n",
    "                else:\n",
    "                    down = grid[i + 1][j]\n",
    "                grid[i][j] += min(right, down)\n",
    "        # print(grid)\n",
    "        return grid[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid):\n",
    "        \"\"\"\n",
    "        64. Minimum Path Sum\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # if(grid)\n",
    "        row=len(grid)\n",
    "        col=len(grid[0])\n",
    "        cost=[[0]*col for i in range(row)]\n",
    "        cost[row-1][col-1]=grid[row-1][col-1]\n",
    "        \n",
    "        i=row-1\n",
    "        for j in range(col-2,-1,-1):\n",
    "            cost[i][j]=cost[i][j+1]+grid[i][j]\n",
    "        j=col-1\n",
    "        for i in range(row-2,-1,-1):\n",
    "            cost[i][j]=cost[i+1][j]+grid[i][j]\n",
    "\n",
    "        for i in range(row-2,-1,-1):\n",
    "            for j in range(col-2,-1,-1):\n",
    "                cost[i][j]=min(cost[i+1][j],cost[i][j+1])+grid[i][j]\n",
    "        \n",
    "        return cost[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not (i==0 and j==0):\n",
    "                    if i==0:\n",
    "                        grid[i][j] = grid[i][j] + grid[i][j-1]\n",
    "                    elif j==0:\n",
    "                        grid[i][j] = grid[i][j] + grid[i-1][j]\n",
    "                    else:\n",
    "                        grid[i][j] = min(grid[i][j]+grid[i-1][j], grid[i][j]+grid[i][j-1])\n",
    "        \n",
    "        print(grid)\n",
    "        return grid[m-1][n-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "\n",
    "    def minPathSum(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not grid:\n",
    "            return 0\n",
    "        row, col = len(grid)-1, len(grid[0])-1\n",
    "        for i in range(1, col+1):\n",
    "            grid[0][i] += grid[0][i-1]\n",
    "        for i in range(1, row+1):\n",
    "            grid[i][0] += grid[i-1][0]\n",
    "        self.res = [[-1 for _ in range(col+1)] for _ in range(row+1)]\n",
    "        return self.recur(row, col, grid)\n",
    "\n",
    "    def recur(self, row, col, grid):\n",
    "        if row == 0 and col == 0:\n",
    "            return grid[0][0]\n",
    "        elif row == 0:\n",
    "            return grid[0][col]\n",
    "        elif col == 0:\n",
    "            return grid[row][0]\n",
    "        elif self.res[row][col] != -1:\n",
    "            return self.res[row][col]\n",
    "        left = self.recur(row, col-1, grid)\n",
    "        top = self.recur(row-1, col, grid)\n",
    "        self.res[row][col] = min(left, top)+grid[row][col]\n",
    "        return self.res[row][col]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        r = len(grid)\n",
    "        c = len(grid[0])\n",
    "        d = [[1000000 for i in range(c)] for j in range(r)]\n",
    "        d[0][0] = grid[0][0]\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if i > 0:\n",
    "                    d[i][j] = min(d[i-1][j] + grid[i][j], d[i][j])\n",
    "                if j > 0:\n",
    "                    d[i][j] = min(d[i][j-1] + grid[i][j], d[i][j])\n",
    "        return d[r-1][c-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not grid:\n",
    "            return 0\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "\n",
    "        dp = [[0 for _ in range(col)] for _ in range(row)]\n",
    "        dp[0][0] = grid[0][0]\n",
    "\n",
    "        for i in range(1, row):\n",
    "            dp[i][0] = dp[i-1][0] + grid[i][0]\n",
    "\n",
    "        for i in range(1, col):\n",
    "            dp[0][i] = dp[0][i-1] + grid[0][i]\n",
    "\n",
    "\n",
    "        for i in range(1, row):\n",
    "            for j in range(1, col):\n",
    "                dp[i][j] = min(dp[i][j-1] + grid[i][j], dp[i-1][j] + grid[i][j])\n",
    "\n",
    "        print(dp)\n",
    "\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not grid:\n",
    "            return 0\n",
    "        \n",
    "        hei = len(grid)\n",
    "        wid = len(grid[0])\n",
    "        dp = [[float('inf') for x in range(wid)] for y in range(hei)]\n",
    "        \n",
    "        end = [wid-1, hei-1]\n",
    "        def dfs(col, row):\n",
    "            if col < 0 or row < 0:\n",
    "                return float('inf')\n",
    "            if dp[row][col] != float('inf'):\n",
    "                return dp[row][col]\n",
    "            if row == 0 and col == 0:\n",
    "                dp[row][col] = grid[0][0]\n",
    "                return dp[row][col]\n",
    "            dp[row][col] = grid[row][col] + min(dfs(col-1, row), dfs(col, row-1))\n",
    "            return dp[row][col]\n",
    "        \n",
    "        return dfs(wid-1,hei-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        if row == 1:\n",
    "            return sum(grid[0])\n",
    "        if col == 1:\n",
    "            res = 0\n",
    "            for item in grid:\n",
    "                res+=item\n",
    "            return res\n",
    "            \n",
    "        for i in range(row-2,-1,-1):\n",
    "            grid[i][col-1] +=grid[i+1][col-1]\n",
    "        for j in range(col-2,-1,-1):\n",
    "            grid[row-1][j] += grid[row-1][j+1]\n",
    "        \n",
    "        for i in range(row-2,-1,-1):\n",
    "            for j in range(col-2,-1,-1):\n",
    "                grid[i][j]+= min(grid[i+1][j],grid[i][j+1])\n",
    "                print(i,j,grid[i][j])\n",
    "        print(grid)\n",
    "        return grid[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid):\n",
    "\n",
    "        dp = [[0 for i in range(len(grid[0]))] for j in range(len(grid))]\n",
    "\n",
    "        for i in range(len(dp)):\n",
    "            for j in range(len(dp[0])):\n",
    "                print(dp[i][j])\n",
    "                dp[i][j] = grid[i][j]\n",
    "                if i > 0 and j > 0:\n",
    "                    dp[i][j] += min(dp[i-1][j],dp[i][j-1])\n",
    "                elif i > 0:\n",
    "                    dp[i][j] += dp[i-1][j]\n",
    "                elif j > 0:\n",
    "                    dp[i][j] += dp[i][j-1]\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        def helper1(sub_m ,sub_n):\n",
    "            if sub_m == 0 and sub_n == 0: return grid[sub_m][sub_n]\n",
    "            if sub_m == 0: return grid[sub_m][sub_n] + helper(sub_m, sub_n-1)\n",
    "            if sub_n == 0: return grid[sub_m][sub_n] + helper(sub_m-1, sub_n)\n",
    "            return grid[sub_m][sub_n] + min(helper(sub_m-1, sub_n), helper(sub_m, sub_n-1))\n",
    "        \n",
    "        \n",
    "        def helper(grid):\n",
    "            m, n = len(grid), len(grid[0])\n",
    "            for sub_m in range(m):\n",
    "                for sub_n in range(n):\n",
    "                    if sub_m == 0 and sub_n == 0: continue\n",
    "                    if sub_m == 0:  \n",
    "                        grid[sub_m][sub_n] += grid[sub_m][sub_n-1]\n",
    "                    elif sub_n == 0: \n",
    "                        grid[sub_m][sub_n] += grid[sub_m-1][sub_n]\n",
    "                    else:\n",
    "                        grid[sub_m][sub_n] += min(grid[sub_m][sub_n-1], grid[sub_m-1][sub_n])\n",
    "            return grid[-1][-1]\n",
    "        \n",
    "        return helper(grid)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum1(self, grid) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        table = [0] * col\n",
    "        for r in range(row):\n",
    "            for c in range(col):\n",
    "                if r == 0:\n",
    "                    if c == 0:\n",
    "                        table[c] = grid[r][c]\n",
    "                    else:\n",
    "                        table[c] = grid[r][c] + table[c-1]\n",
    "                else:\n",
    "                    if c == 0:\n",
    "                        table[c] = grid[r][c] + table[c]\n",
    "                    else:\n",
    "                        min_one = min([table[c], table[c-1]])\n",
    "                        table[c] = grid[r][c] + min_one\n",
    "        return table[col-1]\n",
    "\n",
    "    def minPathSum(self, grid) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        table = [0] * col\n",
    "\n",
    "        for r in range(row):\n",
    "            for c in range(col):\n",
    "                if r == c == 0:\n",
    "                    table[c] = grid[r][c]\n",
    "                elif r == 0 and c > 0:\n",
    "                    table[c] = grid[r][c] + table[c-1]\n",
    "                elif c == 0:\n",
    "                    table[c] += grid[r][c]\n",
    "                else:\n",
    "                    table[c] = grid[r][c] + min([table[c], table[c-1]])\n",
    "        return table[col-1]\n",
    "\n",
    "\n",
    "Solution().minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        dp=[float(\"inf\")]*len(grid[0])\n",
    "        dp[0]=0\n",
    "        # for i in range(1,len(grid[0])):\n",
    "        #     dp[i]=dp[i-1]+grid[0][i]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if j==0:\n",
    "                    dp[0]+=grid[i][j]\n",
    "                else :\n",
    "                    dp[j]=min(dp[j-1],dp[j])+grid[i][j]\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        if not grid: return 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[0] * n] * m\n",
    "        dp[0][0] = grid[0][0]\n",
    "        for i in range(0, m):\n",
    "            for j in range(0, n):\n",
    "                if i == 0:\n",
    "                    if j > 0:\n",
    "                        dp[i][j] = dp[i][j-1] + grid[i][j] \n",
    "                elif j == 0:\n",
    "                    if i > 0:\n",
    "                        dp[i][j] = dp[i-1][j] + grid[i][j]\n",
    "                else:\n",
    "                    dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "\n",
    "        ways = [0] * m\n",
    "        acc = 0\n",
    "        for i in range(0, m):\n",
    "            acc += grid[0][i]\n",
    "            ways[i] = acc\n",
    "        # print(ways)\n",
    "\n",
    "        for j in range(1, n):\n",
    "            for i in range(0, m):\n",
    "                ways[i] = min(ways[i - 1], ways[i]) + grid[j][i]\n",
    "\n",
    "        return ways[m - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        #动态规划，题目如果没有要求的话，尽量先考虑时间复杂度\n",
    "        #可以一步步把去到每个点位都计算出来，因为每个点位只有两种可能，从上往下，或者从做往右，比较大小，记录值即可\n",
    "        #时间复杂度为O(m*n)，因为要遍历每个点位；空间复杂度为O(m*n)，因为要记录每个点位的最小path\n",
    "        path_sum = [[None]*len(grid[0])]*len(grid)\n",
    "        path_sum[0][0] = grid[0][0]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if i==0 and j>0:\n",
    "                    path_sum[i][j] = grid[i][j] + path_sum[i][j-1]\n",
    "                if j==0 and i>0:\n",
    "                    path_sum[i][j] = grid[i][j] + path_sum[i-1][j]\n",
    "                if i>0 and j>0:\n",
    "                    path_sum[i][j] = min(grid[i][j]+path_sum[i-1][j], grid[i][j]+path_sum[i][j-1])\n",
    "        return path_sum[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dp = [0]*n\n",
    "        dp[0] = grid[0][0]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 and j > 0:\n",
    "                    dp[j] = dp[j-1] + grid[i][j]\n",
    "                elif j == 0 and i > 0:\n",
    "                    dp[j] = dp[j] + grid[i][j]\n",
    "                elif j > 0 and i > 0:\n",
    "                    dp[j] = min(dp[j], dp[j-1]) + grid[i][j]\n",
    "        return dp[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        # 条件判断\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if m <= 0 or n <= 0: return 0\n",
    "\n",
    "        # 初始化(1行，所以用列n的值)\n",
    "        dp = [0 for _ in range(n)]\n",
    "        dp[0] = grid[0][0]\n",
    "        for i in range(1, n): dp[i] = dp[i-1] + grid[0][i]\n",
    "\n",
    "        # 状态转移\n",
    "        for i in range(1, m):\n",
    "            # 第 i 行第 0 列的初始值：重点\n",
    "            dp[0] = 0\n",
    "            for ii in range(0, i + 1): dp[0] += grid[ii][0]\n",
    "            \n",
    "            for j in range(1, n):\n",
    "                # print(dp[j-1], dp[j], grid[i][j])\n",
    "\n",
    "                dp[j] = min(dp[j-1], dp[j]) + grid[i][j]\n",
    "            print(dp)\n",
    "        # print(dp)\n",
    "        return dp[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])#获取行和列\n",
    "        dp = grid[:]#复制一份打表格\n",
    "        for i in range(1,m):#初始化第一列\n",
    "            dp[i][0] = dp[i-1][0] + grid[i][0]\n",
    "        for i in range(1,n):#初始化第一行\n",
    "            dp[0][i] = dp[0][i-1] + grid[0][i]\n",
    "#从左边和上边选一个较小的\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                dp[i][j] = min(dp[i][j-1],dp[i-1][j])+grid[i][j]\n",
    "\n",
    "        return dp[-1][-1]#表格的最后一个就是最小的"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        # m = len(grid)\n",
    "        # n = len(grid[0])\n",
    "        # # copy the grid\n",
    "        # sum_dp = grid[:][:]\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         if i > 0 and j > 0:\n",
    "        #             sum_dp[i][j] += min(sum_dp[i-1][j], sum_dp[i][j-1])\n",
    "        #         elif i > 0 and j == 0:\n",
    "        #             sum_dp[i][j] += sum_dp[i-1][j]\n",
    "        #         elif j > 0 and i == 0:\n",
    "        #             sum_dp[i][j] += sum_dp[i][j-1]\n",
    "        # return sum_dp[m-1][n-1]\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        above = grid[0][:]\n",
    "        print(above)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 and j>0:\n",
    "                    above[j] = above[j-1] + grid[i][j]\n",
    "                if j == 0 and i>0:\n",
    "                    above[j] += grid[i][j]\n",
    "                if i > 0 and j > 0:\n",
    "                    left = above[j-1]\n",
    "                    above[j] = min(left, above[j]) + grid[i][j]\n",
    "        return above[n-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = grid[0]\n",
    "        for i in range(1, n):\n",
    "            dp[i] += dp[i - 1]\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                dp[j] += grid[i][j]\n",
    "                if j > 0:\n",
    "                    dp[j] = min(dp[j], dp[j - 1] + grid[i][j])\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = grid[0][:]\n",
    "        for j in range(1,n):\n",
    "            dp[j] += dp[j-1]\n",
    "        dp[0] = 0\n",
    "        for i in range(m):\n",
    "            dp[0] += grid[i][0]\n",
    "            for j in range(1, n):\n",
    "                dp[j] = min(dp[j-1], dp[j]) + grid[i][j]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minPathSum(self, grid: [[int]]) -> int:\n",
    "#         for i in range(len(grid)):\n",
    "#             for j in range(len(grid[0])):\n",
    "#                 if i == j == 0: \n",
    "#                     continue\n",
    "#                 elif i == 0:  \n",
    "#                     grid[i][j] = grid[i][j - 1] + grid[i][j]\n",
    "#                 elif j == 0:  \n",
    "#                     grid[i][j] = grid[i - 1][j] + grid[i][j]\n",
    "#                 else:\n",
    "#                     grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]\n",
    "#         return grid[-1][-1]\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid):\n",
    "        dp = [float('inf')] * (len(grid[0])+1)\n",
    "        dp[1] = 0\n",
    "        for row in grid:\n",
    "            for idx, num in enumerate(row):\n",
    "                dp[idx + 1] = min(dp[idx], dp[idx + 1]) + num\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[0] * n for _ in range(m)]\n",
    "        g = [0] * n\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j == 0:\n",
    "                    g[j] += grid[i][j]\n",
    "                elif i == 0:\n",
    "                    g[j] = g[j - 1] + grid[i][j]\n",
    "                else:\n",
    "                    g[j] = min(g[j-1], g[j]) + grid[i][j]\n",
    "        return g[-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # 初始化\n",
    "        dp = grid[0]\n",
    "        # 第0行\n",
    "        for i in range(1, n):\n",
    "            dp[i] += dp[i-1]\n",
    "        \n",
    "        for i in range(1, m):\n",
    "            # 注意这里\n",
    "            dp[0] += grid[i][0]\n",
    "            for j in range(1, n):\n",
    "                dp[j] = min(dp[j], dp[j-1]) + grid[i][j]\n",
    "        \n",
    "        return dp[-1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        # n, m = len(grid), len(grid[0])\n",
    "        n = grid.__len__()\n",
    "        m = grid[0].__len__()\n",
    "        count = grid[0][0]\n",
    "        dp = list(accumulate(grid[0]))\n",
    "        # for i in range(1,m):\n",
    "        #     dp.append(dp[i-1]+grid[0][i])\n",
    "        # print(dp)\n",
    "        for i in range(1, n):\n",
    "            tmp = [0]*m\n",
    "            count += grid[i][0]\n",
    "            tmp[0] = count\n",
    "            for j in range(1, m):\n",
    "                tmp[j] = min(dp[j], tmp[j-1])+grid[i][j]\n",
    "            dp = tmp\n",
    "        \n",
    "        return dp[m-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        \n",
    "        # dp[0][0] = grid[0][0]\n",
    "        # for i in range(1, m):\n",
    "        #     dp[i][0] = dp[i - 1][0] + grid[i][0]\n",
    "\n",
    "        # for j in range(1, n):\n",
    "        #     dp[0][j] = dp[0][ j - 1] + grid[0][j]\n",
    "\n",
    "        # for i in range(1, m):\n",
    "        #     for j in range(1, n):\n",
    "        #         dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]\n",
    "        # return dp[-1][-1]\n",
    "        \n",
    "        dp = [0 for _ in range(n)]\n",
    "        dp[0] = grid[0][0]\n",
    "        for j in range(1, n):\n",
    "            dp[j] = dp[j - 1] + grid[0][j]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            dp[0] = dp[0] + grid[i][0]\n",
    "            for j in range(1, n):\n",
    "                dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    @lru_cache()\n",
    "    def getMinPath(self, m, n):\n",
    "        if m == self.m and n == self.n:\n",
    "            return self.grid[m][n]\n",
    "        \n",
    "        if m == self.m:\n",
    "            return self.grid[m][n] + self.getMinPath(m, n + 1)\n",
    "        if n == self.n:\n",
    "            return self.grid[m][n] + self.getMinPath(m + 1, n)\n",
    "        \n",
    "        right = self.getMinPath(m, n + 1)\n",
    "        down = self.getMinPath(m + 1, n)\n",
    "        return self.grid[m][n] + min(right, down)\n",
    "    \n",
    "    \n",
    "    def minPathSum(self, grid) -> int:\n",
    "        self.grid = grid\n",
    "        self.m = len(grid) - 1\n",
    "        self.n = len(grid[0]) - 1\n",
    "        return self.getMinPath(0, 0)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ls = [[0]*n]*m\n",
    "        ls[0][0] = grid[0][0]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i > 0 and j > 0:\n",
    "                    ls[i][j] = min(ls[i-1][j],ls[i][j-1]) + grid[i][j]\n",
    "                elif i > 0:\n",
    "                    ls[i][j] = ls[i-1][j] + grid[i][j]\n",
    "                elif j > 0:\n",
    "                    ls[i][j] = ls[i][j-1] + grid[i][j]\n",
    "        return ls[m-1][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [ 0 for _ in range(n)]\n",
    "        dp[0] = grid[0][0]\n",
    "        for j in range(1, n):\n",
    "            dp[j] = dp[j-1]+grid[0][j]\n",
    "            \n",
    "        for i in range(1, m):\n",
    "            dp[0] = dp[0] + grid[i][0]\n",
    "            for j in range(1, n):\n",
    "                dp[j] = min(dp[j-1], dp[j]) + grid[i][j]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        road = [0] * len(grid[0])\n",
    "        road[0] = grid[0][0]\n",
    "        for i in range(1, len(road)):\n",
    "            road[i] = road[i - 1] + grid[0][i]\n",
    "        for i in range(1, len(grid)):\n",
    "            road[0] += grid[i][0]\n",
    "            for j in range(1, len(road)):\n",
    "                road[j] = min(road[j - 1], road[j]) + grid[i][j]\n",
    "        return road[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        res = [[0]*(m+1)]*(n+1)\n",
    "\n",
    "        print(n, m, res)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if i == 0:\n",
    "                    res[i+1][j+1] = res[i+1][j] + grid[i][j]\n",
    "                elif j == 0:\n",
    "                    res[i+1][j+1] = res[i][j+1] + grid[i][j]\n",
    "                else:\n",
    "                    res[i+1][j+1] = min(res[i+1][j], res[i][j+1])+ grid[i][j]\n",
    "        return res[-1][-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if i == j == 0:\n",
    "                    continue\n",
    "                top, left = 200, 200\n",
    "                if i > 0:\n",
    "                    top = grid[i-1][j]\n",
    "                if j > 0:\n",
    "                    left = grid[i][j-1]\n",
    "                grid[i][j] = min(top, left) + grid[i][j]\n",
    "        \n",
    "        return grid[-1][-1]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        # 初始化第一行和第一列\n",
    "        for i in range(1, m):\n",
    "            grid[i][0] += grid[i - 1][0]\n",
    "        for j in range(1, n):\n",
    "            grid[0][j] += grid[0][j - 1]\n",
    "\n",
    "        # 动态规划填充剩余格子\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])\n",
    "\n",
    "        return grid[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: [[int]]) -> int:\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if i == j == 0: continue\n",
    "                elif i == 0:  grid[i][j] = grid[i][j - 1] + grid[i][j]\n",
    "                elif j == 0:  grid[i][j] = grid[i - 1][j] + grid[i][j]\n",
    "                else: grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]\n",
    "        return grid[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        dp[0][0] = grid[0][0]\n",
    "        for i in range(1, m):\n",
    "            dp[i][0] = dp[i-1][0]+grid[i][0]\n",
    "        for j in range(1, n):\n",
    "            dp[0][j] = dp[0][j-1] + grid[0][j]\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]\n",
    "        return dp[m-1][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        dp = [[0 for j in range(n)] for i in range(m)]\n",
    "        dp[0][0] = grid[0][0]\n",
    "        for j in range(1, n):\n",
    "            dp[0][j] = dp[0][j-1] + grid[0][j]\n",
    "        print(dp)\n",
    "        for i in range(1, m):\n",
    "            dp[i][0] = dp[i-1][0] + grid[i][0]\n",
    "        \n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]\n",
    "\n",
    "\n",
    "        return dp[m-1][n-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dp=[[0]*n for _ in range(m)]\n",
    "        for i in range(0,m):\n",
    "            for j in range(0,n):\n",
    "                if i == j == 0: dp[0][0]=grid[0][0]\n",
    "                elif i==0 :\n",
    "                    dp[i][j]=dp[i][j-1]+grid[i][j]\n",
    "                elif j==0 :\n",
    "                    dp[i][j]=dp[i-1][j]+grid[i][j]\n",
    "                else:\n",
    "                    dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]\n",
    "        print(dp)\n",
    "        return dp[-1][-1]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
